The use of data packets is an advantageous format for conveying data messages from originating stations to designated or addressee stations. Data packets typically comprise a fixed number of data bits. Each packet is constructed to include a packet header portion which contains synchronizing or framing data identifying the start of the packet, address data defining the addressee station and other control data information which may include, for example, indications whether the packet is available and/or whether data information has been withdrawn from the packet. The packet is further structured to contain a data portion which accommodates a burst of data destined for the addressee station identified in the header portion.
When a station on a data packet transmission system desires to originate a message, it typically arranges the message into a plurality of data bursts, identifies data packets on the transmission line which are available for transmission, inserts the appropriate address information in the header portion of the available packet and inserts a data burst into the data portion. Advantageously, the originating station also inserts appropriate control information in the header, including information that the packet is now occupied and the data burst therein has not yet been withdrawn by the addressee station. This packet is then conveyed over the transmission system to the addressee station which identifies its own address in the header portion and thereupon withdraws the data burst from the data portion and indicates in the header portion that the packet is available for reuse.
Data packet communication systems have been employed in various different types of systems, one system being the ring or loop system described in "Network for Block Switching of Data" by J. R. Pierce, BSTJ 51, No. 6, July-August 1972, pp 1133-1145. In the Pierce arrangement, a transmission line serially passes from one to another of a plurality of stations arranged in a ring or loop configuration. Data packets are passed from station to station, each station monitoring the packet header to determine if the data burst in the packet is destined for that station. Alternatively, if the station has a message to send, it monitors the packet header to determine if the packet is available. Assuming, in this latter case, that the packet is in fact available, the station thereupon overwrites its address and control information into the packet header and overwrites a data burst into the packet data portion. When the packet arrives at the addressee station, the data burst is then withdrawn and the header information is modified to indicate that the packet is reusable.
In the Pierce arrangement, the packets serially follow one another on the ring. Although only a small proportion of the stations are necessarily involved in transmission at any time, they must monitor the header of each packet to determine if information is directed thereto. Of course, if they intend to send a message, they must also monitor each header to determine if the packet is available. The monitoring of these packet headers must, of course, be done at line speed, which either reduces the speed of the line to accommodate the reading speed of the monitor circuitry of the stations or requires high speed processing apparatus which is consistent with the speed of the loop.
It is understood that, by providing the expedient of time-division or multiplex signaling, a station on a loop may be arranged so that it need not insert or withdraw data at the normally high loop speed. In packet systems, the provision of time-division signaling can be implemented by interleaving each bit (or byte) in each packet with bits in the other packets. The structural format of the signaling system will thus comprise a frame of data constituting a sequence of bits individually obtained from all the packets. The next frame will then comprise a corresponding sequence of the next successive one of the bits from all the packets. An originating or addressee station might then identify a corresponding bit position or time slot in the frames to accommodate bits from the packet that it is sending or receiving and, upon such identification, insert or withdraw only the information in the one corresponding time slot of the several frames and therefore operate at the frame speed which is a fraction of the speed of the line loop. A ring system wherein a station inserts or withdraws data from one time slot of a frame is disclosed in U.S. Pat. No. 3,781,478 issued to D. E. Blahut and F. E. Froehlich on Dec. 25, 1973.
Although insertion and removal of data burst information in a time-division system can be accomplished at frame speed, the processing circuitry for monitoring packet headers cannot achieve this advantage simply by utilizing time-division signaling. A sending station searching for an available packet must monitor the frame and control information in the header of all packets and thus must examine all of the time slots in each of the frames. Accordingly, the processing circuit must scan each time slot in the frame and thus operate at the high line or loop speed. Correspondingly, the processing circuit must examine the address information in each packet header to determine if a packet is directed to that station. Accordingly, it is an object of this invention to provide a multiplexed or interleaved data packet communication system wherein processing circuitry may operate at frame speed rather than at the high loop speed.